public class LiKou {
    public static int i = 0;
    
    public static TreeNode createTree(String str){
        TreeNode root = new TreeNoed(str.charAt(i));
        if(str.charAt(i) != '#'){

            i++;
            root.left = createTree(str);
            root.right = createTree(str);

        }else{
            i++;

        }

        return root;
    }
}
class Solution1 {
    public int tribonacci(int n) {
        int[] dp = new int[n+1];
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 1;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for(int i = 3 ; i <= n ; i++){
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        return dp[n];
    }
}
class Solution2 {
    public int waysToStep(int n) {
        int mod = (int)1e9+7;
        int[] dp = new int[n+1];
        if(n == 0) return 0;
        if(n == 1 ) return n;
        if(n == 2 ) return n;
        if(n == 3 ) return 4;
        dp[0] = 0 ;
        dp[1] = 1 ;
        dp[2] = 2 ;
        dp[3] = 4;

        for(int i = 4 ; i <= n ; i++){
            dp[i] =(( (dp[i-1]%mod) + dp[i-2] ) %mod  + dp[i-3] )% mod;
        }
        return dp[n];

    }
}

class Solution3 {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];

        for(int i = 2 ; i <= n ; i++){
            dp[i] = Math.min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]));

        }
        return dp[n];

    }
}

/*
第五题：路径问题
* */
class Solution5 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        //初始化 ，int类型的二维数组中的值默认是0
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}
/*在二位数组中，如果直接调用b.length方法，返回的则是b数组的行数，
                          如果是b[0].length方法则返回的是0行所代表的长度。

*/
/*
* 路径问题变式，有障碍物的*/
class Solution6 {
    public int uniquePathsWithObstacles(int[][] ob) {
        int m = ob.length;
        int n = ob[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[1][0] = 1 ;
        for(int i = 1 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++ ){
                if(ob[i-1][j-1] == 0){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];

    }
}
class Solution_a {
    public void moveZeroes(int[] nums) {
        int curr = 0 , dest = -1;
        for ( ; curr<nums.length ; curr++ ){
            if (nums[curr] != 0){
                dest++;
                int tem = nums[curr];
                nums[curr] = nums[dest];
                nums[dest] = tem;
            }
        }
    }
}



  class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
    }
  }

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */


/*
 *
 * 检查两棵树是否相同 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(  (  p == null && q != null  )|| ( q == null && p != null)  ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;//尽量都去使用否定句，不怎么怎么样
        }
        return isSameTree(p.left , q.left) && isSameTree (p.right , q.right);
    }
}


/*
 *另一棵树的子树
 * 时间复杂度为  m*n     m，n分别为两棵树的节点个数
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution572 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null ){
            return false;
        }
        if(isSameTree(root , subRoot)){//root的左子树为null的时候第一次递归isSameTree，返回值为false，if语句根本进不去，于是执行下面的代码
            return true;
        }

        if(isSubtree(root.left , subRoot)){   //root.left = null.left 空指针异常
            return true;
        }
        if(isSubtree(root.right , subRoot)){
            return true;
        }
        return false;

    }

    public boolean isSameTree(TreeNode p , TreeNode q){
        if(p == null && q != null  ||  q == null && p != null ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left , q.left) && isSameTree (p.right , q.right);
    }
}

/*
 *翻转二叉树 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution226 {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        //下面三行代码，是代码的优化，树的最后一层能占到整颗树的50%左右，
        // 判断为null后直接就跳出去了
        //不用在遍历最后一层的树了
        if(root.left == null && root.right == null){
            return root;
        }
        TreeNode tem = root.left ;
        root.left = root.right;
        root.right = tem;
        invertTree(root.left);
        invertTree(root.right);
        return root;

    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

/*
* 110. 平衡二叉树
* 时间复杂度为n^2
* 最坏的情况两个函数各自调用了n次
* */

class Solution110 {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.abs(leftHeight-rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);

    }

    public int maxDepth(TreeNode root) {

        if(root == null){
            return 0;
        }

        int leftTreeHeight = maxDepth(root.left);
        int rightTreeHeight = maxDepth(root.right);

        return leftTreeHeight > rightTreeHeight ?  leftTreeHeight+ 1 : rightTreeHeight + 1;
    }

}
/*
 * 110. 平衡二叉树（解法二）
 * 时间复杂度为n^2
 * 最坏的情况两个函数各自调用了n次
 * */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution110_2 {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return maxDepth(root) >= 0 ;
    }

    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftTree = maxDepth(root.left);
        if(leftTree < 0){
            return -1;
        }
        int rightTree = maxDepth(root.right);
        if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree - rightTree)<=1){
            return Math.max(leftTree,rightTree)+1;
        }else{
            return -1;
        }
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */


/*
* 101. 对称二叉树(巨tm有成就感，自己写的差了一点点
* （第二个函数值的返回值有一个&&），案例通过了70%)
* */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricChild(root.left, root.right);

    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if ((leftTree != null && rightTree == null) || (leftTree == null && rightTree != null)) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        if (leftTree.left == rightTree.right && leftTree.right == rightTree.left) {
            return true;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }
}


    /**/

